package 力扣._146_LRU缓存;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

// 超时----主要是找最近最少访问的超时
class LRUCache {

    // 存储值
    Map<Integer, Integer> map;
    // 记录访问记录
    Map<Integer, Integer> visited_time;
    int time = 0;
    int capacity = 0;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        visited_time = new HashMap<>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        // 若存在，则更新访问记录
        if (map.containsKey(key))
            visited_time.put(key, ++time);

        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        // 若存在，则更新访问记录
        if (map.containsKey(key)) {
            visited_time.put(key, ++time);
            map.put(key, value);

        } else {
            // 不存在则插入
            // 1. 加入后未超容量
            if (map.size() < capacity) {
                visited_time.put(key, ++time);
                map.put(key, value);
            } else {
                // 找到最近最少使用的（上次访问时间最小的）
                Set<Integer> set = visited_time.keySet();
                int min_k = -1;
                for (int k : set) {
                    if (min_k == -1)
                        min_k = k;
                    else if (visited_time.get(min_k) > visited_time.get(k))
                        min_k = k;
                }
                // 删除这个
                visited_time.remove(min_k);
                map.remove(min_k);
                // 添加新的
                visited_time.put(key, ++time);
                map.put(key, value);
            }

        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */